﻿//23. 合并 K 个升序链表
//给你一个链表数组，每个链表都已经按升序排列。
//请你将所有链表合并到一个升序链表中，返回合并后的链表。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */


class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        auto cmp = [](const ListNode* a, const ListNode* b)
        {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q;
        for (auto head : lists)
        {
            while (head)
            {
                q.push(head);
                head = head->next;
            }
        }
        ListNode hair;
        auto p = &hair;
        while (!q.empty())
        {
            auto node = q.top();
            q.pop();
            p->next = node;
            p = node;
        }
        p->next = nullptr;
        return hair.next;
    }
};